|
Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. With the advent and popularity of the Internet, there is a need to develop algorithms that do not require any centralized control that have some guarantee of always working correctly. The Byzantine agreement protocol is an essential part of this task. In this article the quantum version of the Byzantine protocol,〔Michael Ben-Or and Avinatan Hassidim, Fast quantum byzantine agreement,STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pg 481-485 ()〕 which works in constant time is described. ==Introduction== The Byzantine Agreement protocol is a protocol in distributed computing. It takes its name from a problem formulated by Lamport, Shostak and Pease in 1982,〔L. Lamport and R. Shostak and M. Pease, The Byzantine Generals Problem, ACM Trans. Program. Lang. Syst., volume 4, number 3, pg 382-401 ()〕 which itself is a reference to a historical problem. The Byzantine army was divided into divisions with each division being led by a General with the following properties: *Each General is either loyal or a traitor to the Byzantine state. *All Generals communicate by sending and receiving messages. *There are only two commands: attack and retreat. *All loyal Generals should agree on the same plan of action: attack or retreat. *A small linear fraction of bad Generals should not cause the protocol to fail (less than a fraction). (See 〔Michael J. Fisher, Nancy A. Lynch,Michael S. Paterson,Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM volume 32, issue=2, pg 374-382 (Impossibility of Distributed Consensus with One Faulty Process )()〕 for the proof of the impossibility result). The problem usually is equivalently restated in the form of a commanding General and loyal Lieutenants with the General being either loyal or a traitor and the same for the Lieutenants with the following properties. *All loyal Lieutenants carry out the same order. *If the commanding General is loyal, all loyal Lieutenants obey the order that he sends. *A strictly less than fraction including the commanding General are traitors. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quantum Byzantine agreement」の詳細全文を読む スポンサード リンク
|